package lc20240606;


import java.util.HashMap;
import java.util.Map;

/**
  * @description 字典树（前缀树）
  * @author 不知名帅哥
  * @date 2024/6/6 14:04
  * @version 1.0
*/
public class Trie {

    TrieNode root;

    public Trie() {
        root=new TrieNode();
    }

    public void insert(String word) {
        char[] curArray=word.toCharArray();
        TrieNode cur=root;
        for (int i = 0; i < curArray.length; i++) {
            if (cur.children.containsKey(curArray[i])){
                cur=cur.children.get(curArray[i]);
            }
            else {
                cur.children.put(curArray[i],new TrieNode());
                cur=cur.children.get(curArray[i]);
            }
        }
        //设置最后一位为true
        cur.isWord=true;
    }

    public boolean search(String word) {
        TrieNode cur=root;
        char[] charArray = word.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            cur = cur.children.get(charArray[i]);
            //如果没遍历到末尾，返回false
            if (cur==null){
                return false;
            }
        }
        return cur.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur=root;
        char[] charArray = prefix.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            cur = cur.children.get(charArray[i]);
            //如果没遍历到末尾，返回false
            if (cur==null){
                return false;
            }
        }
        return true;
    }
}

//class TrieNode {
//    Map<Character, TrieNode> children = new HashMap<>();
//    String word = null;
//}

//class Trie {
//    TrieNode root;
//
//    public Trie() {
//        root = new TrieNode();
//    }
//
//    public void insert(String word) {
//        TrieNode node = root;
//        for (char c : word.toCharArray()) {
//            if (!node.children.containsKey(c)) {
//                node.children.put(c, new TrieNode());
//            }
//            node = node.children.get(c);
//        }
//        node.word = word;
//    }
//}
